package top.minuy.structure.graph.bipartition.bfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 检测二分图，广度优先遍历
 *
 * @author Minuy
 * @time 10:46
 * @date 2021/11/20
 */
public class BipartitionDetection {
    public final static int BLUE = 1;
    public final static int GREEN = 2;

    private Graph g;
    private boolean[] isVisited;
    private int[] colors;
    private boolean isBipartition;

    public BipartitionDetection(Graph g) {
        this.g = g;

        if (g.isDirected()){
            throw new IllegalArgumentException("BipartiteMatching only works in undirected graph.");
        }

        isVisited = new boolean[g.V()];
        isBipartition = true;
        colors = new int[g.V()];

        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                if (!bfs(v, BLUE)) { // 如果有冲突了
                    isBipartition = false;
                    break;
                }
                // System.out.println("根顶点："+v);
            }
        }
    }

    private boolean bfs(int v, int color) {
        List<Integer> queue = new ArrayList<>();
        queue.add(v); // 根顶点入队
        isVisited[v] = true; // 入队的时候设置为true
        colors[v] = color;
        // System.out.println("根顶点入队："+v);
        // System.out.println("==============");
        while (!queue.isEmpty()) {
            // 第一个元素出队
            v = queue.remove(0);
            // System.out.println("第一个元素出队并访问："+v);

            // 设置父节点的颜色
            color = colors[v];

            // 访问
            // order.add(v);

            for (int w : g.adj(v)) {
                if (!isVisited[w]) {  // 如果没被访问过
                    queue.add(w);  // 入队
                    // System.out.println("子顶点入队："+w);
                    isVisited[w] = true; // 入队的时候设置为true

                    if (color == BLUE) {
                        colors[w] = GREEN;
                    } else if (color == GREEN) {
                        colors[w] = BLUE;
                    }
                } else if (colors[w] == color) { // 如果被访问过了，并且颜色和本顶点相同，冲突
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 查询是不是二分图
     *
     * @return boolean 是否是二分图
     * @author Minuy
     * @date 2021/11/20 10:57
     */
    public boolean isBipartition() {
        return isBipartition;
    }

    /**
     * 获取一部分
     *
     * @param color 颜色
     * @return Iterable<Integer>
     * @author Minuy
     * @date 2021/11/20 10:57
     */
    private Iterable<Integer> getPart(int color) {
        if (isBipartition()) {
            ArrayList<Integer> ret = new ArrayList<>();
            for (int v = 0; v < colors.length; v++) {
                if (colors[v] == color) {
                    ret.add(v);
                }
            }
            return ret;
        } else {
            throw new IllegalArgumentException("Graph is not a BipartitionGraph.");
        }
    }


    /**
     * 获取蓝色分部
     *
     * @return Iterable<Integer> 蓝色分部数组
     * @author Minuy
     * @date 2021/11/19 20:56
     */
    public Iterable<Integer> blue() {
        return getPart(BLUE);
    }

    /**
     * 获取绿色分部
     *
     * @return Iterable<Integer> 绿色分部数组
     * @author Minuy
     * @date 2021/11/19 20:56
     */
    public Iterable<Integer> green() {
        return getPart(GREEN);
    }
}
